备用返回通道
题目链接:牛客网
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format:%lld
题目描述:
小红拿到了一棵树,她想请你寻找一条简单路径,使得这条路径不重不漏的经过所有节点。如果不存在这样的简单路径,则直接输出 -1
。
简单路径是指这样一条路径,其经过的顶点和边互不相同。
输入描述:
- 第一行输入一个正整数 $ n $ ($ 2 \leq n \leq 10^5 $),代表树的节点数量。
- 此后 $ n-1 $ 行,第 $ i $ 行输入两个正整数 $ u_i, v_i $ ($ 1 \leq u_i, v_i \leq n; u_i \neq v_i $),代表第 $ i $ 条边连接节点 $ u_i $ 和节点 $ v_i $。
输出描述:
如果不存在这样的简单路径,直接输出
-1
;否则,在一行上输出两个整数 $ x, y $,代表你所找到的简单路径的起点和终点。 如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。 示例1
输入:4 1 3 2 1 3 4
输出:
2 4
说明: 在这个样例中,输出
4 2
也是正确的答案。